package 学习计划.算法基础;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 搜索
 */
public class Study08 {

    public static void main(String[] args) {

        Study08 impl = new Study08();
        System.out.println(impl.shortestPathBinaryMatrix2(new int[][]{
                {0, 1, 0, 0, 1, 1, 0},
                {1, 0, 0, 0, 0, 0, 0},
                {1, 0, 0, 1, 1, 1, 1},
                {0, 1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 0, 0, 1, 0, 0, 0},
                {1, 0, 1, 0, 0, 1, 0}
        }));

    }

    //1091. 二进制矩阵中的最短路径
    //给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
    //
    //二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
    //
    //路径途经的所有单元格都的值都是 0 。
    //路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
    //畅通路径的长度 是该路径途经的单元格总数。

    /**
     * 深度优先搜索+回溯
     */
    public int shortestPathBinaryMatrix(int[][] grid) {
        dfs(grid, 0, 0, 1);

        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
    }

    private void dfs(int[][] grid, int row, int column, int curDistance) {
        if (grid[row][column] == 1) {
            return;
        }
        grid[row][column] = 1;
        if (row == grid.length - 1 && column == grid[0].length - 1) {
            minDistance = Math.min(minDistance, curDistance);
        }

        for (int[] direct : direction) {
            int nextRow = row + direct[0];
            int nextColumn = column + direct[1];
            if (nextRow >= 0 && nextRow < grid.length && nextColumn >= 0 &&
                    nextColumn < grid[0].length && grid[nextRow][nextColumn] == 0) {
                dfs(grid, nextRow, nextColumn, curDistance + 1);
                grid[nextRow][nextColumn] = 0;
            }
        }
    }

    private int minDistance = Integer.MAX_VALUE;
    private int[][] direction = {{-1, 0}, {-1, -1}, {-1, 1}, {0, -1}, {0, 1}, {1, 0}, {1, 1}, {1, -1}};

    /**
     * 广度优先搜索
     */
    public int shortestPathBinaryMatrix2(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{0, 0});
        grid[0][0] = 1;

        int curDistance = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            curDistance++;
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                if (cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1) {
                    return curDistance;
                }

                for (int[] direct : direction) {
                    int nextRow = cur[0] + direct[0];
                    int nextColumn = cur[1] + direct[1];
                    if (nextRow >= 0 && nextRow < grid.length && nextColumn >= 0 &&
                            nextColumn < grid[0].length && grid[nextRow][nextColumn] == 0) {
                        queue.addLast(new int[]{nextRow, nextColumn});
                        grid[nextRow][nextColumn] = 1;
                    }
                }
            }
        }
        return -1;
    }

    //130. 被围绕的区域
    //给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，
    //并将这些区域里所有的 'O' 用 'X' 填充。

    /**
     * 标记 + 深度优先搜索
     * 将边界的 O 和其相邻的 O ，全部标记起来，其余全部变成 X
     */
    public void solve(char[][] board) {
        boolean[][] visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            dfs(i, 0, board, visited);
            dfs(i, board[0].length - 1, board, visited);
        }

        for (int j = 0; j < board[0].length; j++) {
            dfs(0, j, board, visited);
            dfs(board.length - 1, j, board, visited);
        }
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[0].length; j++) {
                if (visited[i][j]) {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private int[][] direct = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private void dfs(int i, int j, char[][] board, boolean[][] visited) {
        if (board[i][j] == 'X') return;
        visited[i][j] = true;
        board[i][j] = 'X';

        for (int[] d : direct) {
            int nextI = i + d[0];
            int nextJ = j + d[1];
            if (nextI >= 0 && nextI < board.length && nextJ >= 0 &&
                    nextJ < board[0].length &&
                    board[nextI][nextJ] == 'O') {
                dfs(nextI, nextJ, board, visited);
            }
        }
    }
}
